package org.example.SolutionNew001;

public class Array01 {
    public static void main(String[] args) {
        Array01 a = new Array01();
        int[] nums=new int[]{5,4,-1,7,8};
        System.out.println(a.maxSubArray(nums));
    }

    public int maxSubArray1(int[] nums) {
        int n=nums.length;
        int[] helper=new int[n];
        helper[0]=nums[0]; int res=nums[0];
        for(int i=1;i<n;i++){
            helper[i]=Math.max(nums[i],helper[i-1]+nums[i]);
            res=Math.max(res,helper[i]);
        }
        return res;
    }

    //优化
    public int maxSubArray(int[] nums) {
        int pre=0,res=nums[0];
        for(int num:nums){
            pre=Math.max(pre+num,num);
            res=Math.max(res,pre);
        }
        return res;
    }
}
